1. Field of the Invention
This invention relates to signal decoding apparatus and more particularly to an improved Viterbi decoder capable of decoding convolutional codes with constraint lengths up to about 15 and code rates of one-half to one-sixth.
2. Description of the Prior Art
A search of the prior art has revealed the following patents:
3,789,360 . . . Clark, Jr., et. al. PA1 4,630,032 . . . Gordon et. al. PA1 4,715,037 . . . Yagi PA1 4,730,322 . . . Pollara-Bozzola PA1 4,748,626 . . . Wong PA1 4,015,238 . . . Davis PA1 4,493,082 . . . Cumberton et al. PA1 4,500,994 . . . McCallister et al. PA1 4,545,054 . . . Davis
Of the above-noted patents the closest one to the principles of this invention is the one by Pollara-Bozzola ('322 patent) in which a hypercube method and apparatus for formulating a Viterbi decoder is defined and claimed. The trellis comprises states that are assigned to nodes of the hypercube according to a novel algorithm and thus allow for highly parallel Viterbi decoder structures. The issue of how to formulate higher constraint length viterbi decoders, with a practical size, speed, and with efficient wiring of modules operating in parallel, however, is not addressed in this prior art reference. The remaining prior art patents do not teach or suggest the novelty that is described and claimed in this application.
Some additional references of which the inventors are aware are listed in keeping with the inventor's duty of disclosure. Such references are of interest only and include:
Numerous textbooks teach the operation and structure of Viterbi decoding. It is well known that if one wants to increase the constraint length of a Viterbi decoder one must double the number of states in the trellis diagram used for evaluating the various possibilities contained in an input string of convolutionally encoded data to be decoded. It is readily apparent that, as one increases the constraint length, the size and complexity of the decoder grows exponentially. The complexity of the structure, although simple from a theoretical standpoint becomes a packaging nightmare.
A Viterbi decoder finds the maximum-likelihood path through a state trellis, based on the information contained in a stream of encoded symbols, and yields a sequence of decoded information bits. At each information bit time, each state in the trellis must select one of the two possible paths coming into the state. These decisions are based on the accumulated metrics into each state, which represent the likelihood of reaching that state. The accumulated metrics are updated, at each information time, by adding to the previously computed accumulated metric the branch metric associated with the newly received symbols. This viterbi decoding sequence is well known and is implicit in this disclosure. This invention will focus on overcoming the bottleneck of partitioning, packaging and duplicating the electrical circuits needed for long constraint length decoders (K=7, 8, 9, 15, etc.) that must operate at high decoding speeds (one million bits per second and higher).
Since a constraint length 15 Viterbi decoder has 2.sup.14 such trellis states it is a formidable problem to implement the decoder by distributed architecture that makes high decoding speed feasible. When such a decoder is implemented in a fully parallel format, the number of wires and decision making processors totals into the thousands. The longer the constraint length, the more non-trivial the packaging and formulating problem becomes. For example, consider the clocking associated with the decision making processors. Data must be delivered to every processor at the same interval. Even with today's integrated chip technology, the Viterbi decoder's timing, structural, architecture and wiring complexity is a staggering undertaking.
Our invention, for the first time, discloses such high speed long constraint length decoders formulated into a practical system that is compatible with today's technology.